#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    struct node *left;
    struct node *right;
    char ch;
} tree_node;

tree_node *create_tree(char *ch, char node_name)
{
    tree_node *n = (tree_node *)malloc(sizeof(tree_node));
    printf("please input %c->%s: ", node_name, ch);
    scanf("%c", &n->ch);
    getchar();

    if (n->ch != '#') {
        n->left = create_tree("left", n->ch);
        n->right = create_tree("right", n->ch);

        return n;
    } else {
        return NULL;
    }
}

void show_tree_root(tree_node *T)
{
    if (NULL == T) {
        return;
    }

    printf("%c ", T->ch);
    show_tree_root(T->left);
    show_tree_root(T->right);
}

void show_tree_middle(tree_node *T)
{
    if (NULL == T) {
        return ;
    }

    show_tree_middle(T->left);
    printf("%c ", T->ch);
    show_tree_middle(T->right);
}

void show_tree_end(tree_node *T)
{
    if (NULL == T) {
        return ;
    }

    show_tree_end(T->left);
    show_tree_end(T->right);
    printf("%c ", T->ch);
}

void free_tree(tree_node **T)
{
    if (NULL == *T) {
        return ;
    }

    free_tree( &((*T)->left) );
    free_tree( &((*T)->right)  );

    printf("节点 %c 释放\n", (*T)->ch);
    free(*T);
    *T = NULL;
}

int main(int argc, char *argv[])
{
    tree_node *T = NULL;
        
    T= create_tree("root", ' ');

    printf("root: ");
    show_tree_root(T);
    putchar('\n');

    printf("middle: ");
    show_tree_middle(T);
    putchar('\n');


    printf("root: ");
    show_tree_end(T);
    putchar('\n');

    free_tree(&T);

    return 0;
}
